\documentclass[a4paper]{article}

\usepackage{graphics} % for pdf, bitmapped graphics files
\usepackage{times} % assumes new font selection scheme installed
\usepackage{verbatim}
\usepackage{natbib}
\usepackage{color}
\usepackage{url}
\usepackage{graphicx}
\usepackage[ruled,linesnumbered,vlined]{algorithm2e}
\usepackage{amsmath,amsfonts,amssymb,bm,amsthm}
\usepackage{listings}

%\lstdefineformat{prompt}{~=\( \sim \)}
%\lstset{basicstyle=\ttfamily,format=prompt}
\lstset{basicstyle=\ttfamily}

%From mitko
\newcommand{\subst}[2]{(#1 \leftarrow #2)}
\newcommand{\proj}[2]{\left.#1\right|_{#2}}

\newcommand{\mbm}[1]{\mbox{\boldmath $#1$}}
%\usepackage{tabularx,colortbl}
\usepackage{bbm} % bbm fonts
\usepackage{subfigure}  % use for side-by-side figures
%\usepackage{hyperref}   % use for hypertext links, including those to external documents and URLs
\usepackage{soul}
\usepackage{cleveref}

%COLORS
\definecolor{gray}{rgb}{0.8,0.8,0.8}\newcommand{\gray}{\color{gray}}
\definecolor{darkgray}{rgb}{0.6,0.6,0.6}\newcommand{\darkgray}{\color{darkgray}}
\definecolor{white}{rgb}{1.0,1.0,1.0}\newcommand{\white}{\color{white}}
\definecolor{blue}{rgb}{0.0,0.0,1.0}\newcommand{\blue}{\color{blue}}
\definecolor{mygray}{rgb}{0.8,0.8,0.8}\newcommand{\mygray}{\color{mygray}}
\definecolor{mydarkgray}{rgb}{0.6,0.6,0.6}\newcommand{\mydarkgray}{\color{mydarkgray}}
\definecolor{mydarkgrayA}{rgb}{0.3,0.3,0.3}\newcommand{\mydarkgrayA}{\color{mydarkgrayA}}
\definecolor{mywhite}{rgb}{1.0,1.0,1.0}\newcommand{\mywhite}{\color{mywhite}}

% Federico's gray box
\newcommand{\graybox}[1]{\vspace{0.3cm}\noindent
  \fcolorbox{black}{mygray}{\parbox{0.985\textwidth}{#1}}
\vspace{0.3cm}}

% Federico's gray box w/ title
\newcommand{\grayboxt}[2]{\vspace{0.3cm}\noindent
%  \fcolorbox{black}{mygray}{\parbox{0.985\textwidth}{{\bf #1} #2}}
  \fcolorbox{black}{mygray}{\begin{minipage}{0.985\textwidth}{\bf #1} #2\end{minipage}}
\vspace{0.3cm}}

% Mitko's gray box
\newcommand{\gbox}[1]{
  \begin{center}
    \fcolorbox{black}{gray}{
      \begin{minipage}[b]{0.98\textwidth}
        \begin{center}
          %\vspace{2mm}
          \begin{minipage}{0.97\textwidth}
            #1 
          \end{minipage}
          \vspace{2mm}
        \end{center}
      \end{minipage}
    }
  \end{center}
}

% Mitko's white box
\newcommand{\wbox}[1]{
  \begin{center}
    \fcolorbox{black}{white}{
      \begin{minipage}[b]{0.98\textwidth}
        \begin{center}
          %\vspace{2mm}
          \begin{minipage}{0.97\textwidth}
            #1 
          \end{minipage}
          \vspace{2mm}
        \end{center}
      \end{minipage}
    }
  \end{center}
}


\newtheorem{theo}{Theorem}
\newtheorem{defin}{Definition}
\newtheorem{reduction}{Reduction}
\newtheorem{prop}{Property}
\newtheorem{remark}{Remark}
\newtheorem{lemma}{Lemma}
\newtheorem{coro}{Corollary}
\newtheorem{scen}{Scenario}
\newtheorem{ex}{Exercise}

\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\argmax}{arg\,max}

\title{Advanced Aritificial Intelligence (DT4048)\\{\em Lab 1: Uninformed and Informed Search}}

\author{Masoumeh Mansouri, Federico Pecora\\Center for Applied Autonomous Sensor Systems\\\"Orebro University, SE-70182 Sweden\\\url{{masoumeh.mansouri, federico.pecora}@oru.se}}

\date{Fall term 2014 (HT2014)}

\begin{document}

\maketitle

\section{Introduction}

In this lab we explore the practical aspects of uninformed and informed (heuristic) search.  Our running example is the well-known {\bf Rubik's Cube} combinatorial puzzle.
\begin{figure}[!ht]
\centering
\input{fig/rc.pdf_t}
\caption{{\small The Rubik's cube puzzle was invented by Hungarian architect Ern\H{o} Rubik in 1975.}}
\label{fig:rc}
\end{figure}
The objective is to achieve, by rotating the veritcal or horizontal ``discs'' of the cube, a configuration where all faces have one color (see Fig.~\ref{fig:rc}).  In this lab, we will work on solving the Rubik's Cube puzzle with uninformed and informed search techniques.  Please take a moment to recall the theory covered in class --- see parts 1--3 of the course slides at \url{aass.oru.se/~fpa} or on Blackboard.

\section{Setup}
The codebase you will be using in this lab depends on the Java implementation of the AIMA library (\url{aima-java.googlecode.com}).  The necessary libraries are already included in the codebase.
%automatically downloaded by the build environment which you will use to build the codebase (Gradle).
Open a command prompt, and check out the lab codebase as follows:
\begin{lstlisting}
$ svn checkout http://advanced-ai-lab-dt4048.\
googlecode.com/svn/trunk/ advanced-ai-lab-dt4048
\end{lstlisting}
Build the codebase with Gradle:
\begin{lstlisting}
$ cd advanced-ai-lab-dt4048
$ gradle install
\end{lstlisting}
If no errors were encountered, you can now use Gradle to automatically set up an Eclipse project:
\begin{lstlisting}
$ gradle eclipse
\end{lstlisting}
On the PCs in T002, issuing command {\tt eclipse} starts the Eclipse C/C++ IDE.  For this lab you need the Eclipse Java IDE, which is started as follows:
\begin{lstlisting}
$ cd
$ eclipse/eclipse
\end{lstlisting}
Once you have launched the Eclipse Java IDE, create a new Java project, de-select ``Use default location'', and browse to the path of the downloaded codebase. You are now ready to start!

\section{Representation}
The first step in achieving an automated procedure for solving any problem is to decide on a representation to use for describing the {\em states} explored during search.  Many representations are possible for the Rubik's Cube, and we have implemented one for you.

\begin{figure}[!ht]
\centering
\input{fig/rcState.pdf_t}
\caption{{\small Elements used to represent the state of the Rubick's Cube.}}
\label{fig:rcState}
\end{figure}

A state is represented by a 3D array of {\tt Cubie} objects, each of which represents one of the 27 small cubes in the Rubik's Cube.  Each {\tt Cubie} has 6 {\tt Face}s, but not all of them are visible.  A Rubik's Cube is an instance of class {\tt RubiksCube}, which maintains the 3D array of {\tt Cubie}s and provides the methods that implement the moves (i.e., how the state of the Rubik's Cube is altered by each move).  By convention (see Figure~\ref{fig:rcState}), the yellow face is the ``front'' face, the white face is the ``back'' face, the red face is the ``top'' face, the green face is the ``left'' face, the blue face is the ``right'' face, and the orange face is the ``bottom'' face.  

The moves are defined as in Figure~\ref{fig:rcMoves}.  Note that in a $3 \times 3$ Rubik's Cube the center {\tt Cubie}s remain fixed, e.g., the middle of the ``front'' face will always be yellow.  Hence, there is no need to define a move for rotating the ``center'' disc.

\begin{figure}[!ht]
\centering
\input{fig/rcMoves.pdf_t}
\caption{{\small Moves used to expand states: {\tt FRONT} and {\tt LEFT} (shown), {\tt RIGHT}, {\tt BACK}, {\tt TOP}, {\tt BOTTOM}, and their inverses.}}
\label{fig:rcMoves}
\end{figure}

The constructor {\tt RubiksCube(n,m)} can be invoked to create an initial state for the Rubik's Cube problem, where {\tt n} is the dimension of the Rubik's Cube, and {\tt m} is a seed for creating an initial unsolved state.  In this lab, we will focus on cubes with $2 \leq \text{{\tt n}} \leq 3$, although the implementation can be easily extended to accommodate $\text{{\tt n}} > 3$.  The creation of an initial state based on {\tt m} consists of applying {\tt m} random moves to the goal state.  You can use larger values of {\tt m} to create more challenging problems --- not, however, that {\tt m} is not a good estimator of problem difficulty.

In this lab we will use the AIMA implementations of uninformed and informed search algorithms.  To create a problem, four ingredients are needed: a {\tt RubiksCube} (which represents the initial state), a {\tt RubiksCubeFunctionFactory} (which provides the list of actions through methods {\tt getSymmetricActionsFunction()} and {\tt getAsymmetricActionsFunction}), a function to compute the state resulting from the application of a given action (method {\tt getResultFunction()} of class {\tt RubiksCubeFunctionFactory}), and a {\tt RCgoalTest} (which provides the goal test function):

\begin{lstlisting}
Problem problem =
  new Problem(rubiksCube,
    RubiksCubeFunctionFactory.getSymmetricActionsFunction(),
    RubiksCubeFunctionFactory.getResultFunction(),
    new RCgoalTest());
\end{lstlisting}

\noindent A search algorithm (e.g., Breadth First Search) is instantiated as follows:

\begin{lstlisting}
Search srch = new BreadthFirstSearch(new TreeSearch());
\end{lstlisting}

\noindent and search is involked by calling the method {\tt srch.search(problem)}.  Note that tree search was used in the example --- a {\tt GraphSearch} class is also provided.  Class {\tt TestRubiksCube} contains an initial example to start with.

\section{Uninformed Search Strategies}

{\ex{}\label{ex:ex1} Which among Breadth First Search and Depth First Search is more likely to solve a Rubik's Cube?  Write down your hypothesis, then solve a randomly generated Rubik's Cube.  Explain in writing the results you observe.\vspace{0.1cm}}

{\ex{}\label{ex:ex2} Why does using Graph Search alter the results of the previous exercise?  How in particular does this affect DFS?\vspace{0.1cm}}

{\ex{}\label{ex:ex3} What does this mean, and when do you encounter this problem?  
\begin{lstlisting}
Exception in thread "main" java.lang.OutOfMemoryError:
  GC overhead limit exceeded
    at RubiksCube.copyFaces(RubiksCube.java:316)
    at RubiksCube.rotate(RubiksCube.java:436)
        ...
\end{lstlisting}
How can the problem be overcome (without using heuristics)?  Try your solution and write down your observations.
\vspace{0.1cm}}

{\ex{}\label{ex:ex4} The moves you have used so far generate a symmetric search space, meaning that for all moves there exists an inverse (e.g., the changes brought about by action {\tt FRONT} are undone by action {\tt FRONTI}).  Can we remove the inverse moves? Is this true in general or only for the Rubik's Cube? Try the search strategies in Exercises~\ref{ex:ex1}--\ref{ex:ex3} with the modified action set --- to do so, replace the call to factory method
\begin{lstlisting}
RubiksCubeFunctionFactory.getSymmetricActionsFunction()
\end{lstlisting}
with
\begin{lstlisting}
RubiksCubeFunctionFactory.getAsymmetricActionsFunction()
\end{lstlisting}
\vspace{0.1cm}}


\section{Informed Search Strategies}
A possible heuristic for the Rubik's Cube is the number of {\tt Cubie}s that are not in the goal position.  An implementation of this heuristic is provided for you in the codebase (see class {\tt MisplacedCubiesNotAdmissible}).

{\ex{}\label{ex:ex5} The {\tt MisplacedCubiesNotAdmissible} heuristic is not admissible --- why?  Modify the heuristic to make it admissible and implement it as class {\tt MisplacedCubiesAdmissible}. Run $\text{A}^\star$ with the new heuristic and compare the results obtained with the non-admissible one.\vspace{0.1cm}}

{\ex{}\label{ex:ex6} Run $\text{A}^\star$ with the {\tt MisplacedCubiesAdmissible} heuristic and compare the results obtained with the non-admissible one.\vspace{0.1cm}}

{\ex{}\label{ex:ex7} Implement the 3D Manhattan distance heuristic for the Rubik's Cube.  Why is 3D Manhattan distance not admissible?  Modify it to make it admissible, run $\text{A}^\star$ with the new heuristic and compare to the results obtained in Exercise~\ref{ex:ex6}.\vspace{0.1cm}}

{\ex{}\label{ex:ex8} There are fewer corner cubies than there are edge cubies, hence the expected 3D Manhattan distance of corner cubies is lower.  Implement the heuristic {\tt CornerManhattanDistance}, which computes the sum of 3D Manhattan distances of corner cubies, and {\tt EdgeManhattanDistance}, which does the same but only for edge cubies.  Note that 3D Manhattan distance alone is not admissible --- how should it be modified so that it is?  Which among {\tt CornerManhattanDistance} and {\tt EdgeManhattanDistance} will perform better?  Write your thoughts before implemneting the heursitics, then verify with your implementation.\vspace{0.1cm}}

{\ex{}\label{ex:ex9} Devise and implment a heuristic that is guaranteed to perform better than (or at most as well as) all heuristics you have used so far.\vspace{0.1cm}}

{\ex{}\label{ex:ex10} It has been shown that $\text{IDA}^\star$ achieves the best performance on the Rubik's Cube puzzle.  Implement this algorithm and verify this claim.\vspace{0.1cm}}

%\bibliographystyle{apalike}
%\bibliography{metaCSP}

\end{document}

